package com.itheima.binarysearch;

public class BinarySearchBasic {
    public static void main(String[] args) {
        int[] arr = {3,6,7,9,10,15,19,28,31,40};
        System.out.println(binarySearch(arr, 40));

    }

    public static int binarySearch(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        //问题1:为什么是i <= j意味着区间内有未比较的元素,而不是i < j
        //  i,j 它们指向的元素也会参与比较
        //  i<j 只意味着m指向的元素参与比较
        while (i <= j) {
            //问题2 : (i + j) / 2有问题吗?
            //  >> 正数补0 负数补1    >>> 负数正数都补0
            int m = (i + j) >>> 1;  //无符号右移等于除以2
            if (target < arr[m]) {
                j = m - 1;
            }else if (arr[m] < target){
                i = m + 1;
            }else {
                return m;
            }
        }
        return -1;
    }
}
